Termity [A]

Limit pamięci: 256 MB

Dwa termity postanowiły zjeść stary, drewniany płot. Płot ów składa się z sztachet, których wysokości niekoniecznie są jednakowe. Termity pożarły już część z nich, ale stwierdziły, że warto tę pracę urozmaicić. Zdecydowały zagrać w grę i jeść na przemian po jednej sztachecie. Termit w przypadającej na niego kolejce może wybrać do zjedzenia tylko taką sztachetę, która sąsiaduje z jakąś wcześniej pożartą sztachetą. Wiedząc, że każdy z termitów tak wybiera sztachety, by w ciągu całej gry suma wysokości zjedzonych przez niego sztachet była jak największa, oblicz, ile drewna przypadnie każdemu z nich w udziale.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita (), określająca liczbę sztachet w płocie. Drugi wiersz zawiera ciąg liczb całkowitych (), opisujących wysokości kolejnych sztachet, przy czym oznacza zjedzoną sztachetę. Sztacheta o numerze (dla ) sąsiaduje ze sztachetami o numerach oraz , sztacheta o numerze sąsiaduje tylko ze sztachetą o numerze , a sztacheta o numerze tylko ze sztachetą o numerze . Co najmniej jedna z liczb na wejściu będzie równa zeru.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia należy wypisać dwie liczby całkowite. Pierwsza z nich określa sumę wysokości sztachet, którymi pożywi się termit rozpoczynający rozgrywkę, zaś druga, ile drewna przypadnie jego przeciwnikowi.

Przykład

Dla danych wejściowych:

8
1 2 0 3 7 4 0 9

poprawną odpowiedzią jest:

17 9

Wyjaśnienie do przykładu: Płot składał się z 8 sztachet, z których 2 już są zjedzone. Pierwszy termit w pierwszym ruchu może wybrać sztachety o wysokościach 2, 3, 4 lub 9. W trakcie optymalnej rozgrywki jedzone będą kolejno sztachety o wysokościach 9, 2, 1, 4, 7 i 3.

Autor zadania: Tomasz Idziaszek.